#include <iostream>
using namespace std;
#include <cstring>
#include <queue>

// n表示点的数量，m表示边的数量
/*********************** 单源最短路径 *************************/
// 一、边权都为正数
/* 1、朴素版Dijkstra  O(n^2) */
// Dijkstra求最短路: https://www.acwing.com/problem/content/description/851/
/*
const int N = 510;
int g[N][N];
int dist[N];  // dist[i]: i到源点的距离
bool view[N]; // view[i]: i是否已确定最短距离
int n, m;

// 每次从 未确定最短路的点中 找出距离源点最近的点，将其加入到已确定最短路的点，再进行松弛操作
int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; ++i)
    {
        // 找距离源点最近的点
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!view[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        // 小优化
        if (t == n)
            break;
        view[t] = true; // 加入到已确定最短路的点
        // 松弛操作
        for (int j = 1; j <= n; ++j)
            if (g[t][j] != 0x3f3f3f3f && dist[j] > dist[t] + g[t][j])
                dist[j] = dist[t] + g[t][j];
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
}
int main()
{
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof g);
    int a, b, c;
    while (m--)
    {
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = min(g[a][b], c); // 会有重边
    }
    int ans = Dijkstra();
    printf("%d", ans);
    return 0;
}*/

/* 2、堆优化版Dijkstra   O(mlogn)*/
// Dijkstra求最短路: https://www.acwing.com/problem/content/description/852/
// //每次拿距离源点最近的点，加入到已确定最短路径的点的集合，更新其他点到源点的最短距离
/*
const int N = 2e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];  //dist[i] 源点到i的最短距离
bool view[N]; //view[i]表示i是否已确定最短路径
pair<int,int> heap[N];
int sz; //记录heap的实际大小
int n, m;

void down(int p)
{
    int l = 2 * p + 1;
    if(l >= sz) return;
    if(l + 1 < sz && heap[l + 1] < heap[l]) ++l;
    if(heap[p] > heap[l])
    {
        swap(heap[p], heap[l]);
        down(l);
    }
}
void up(int i)
{
    if(i <= 0) return;
    int p = (i - 1) / 2;
    if(heap[p] > heap[i])
    {
        swap(heap[p], heap[i]);
        up(p);
    }
}
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    heap[sz++] = { 0,1 };
    //up(sz - 1);
    while(sz)
    {
        //每次拿距离源点最近的点，加入到已确定最短路径的点的集合，更新其他点到源点的最短距离
        auto[d, ver] = heap[0];
        swap(heap[0], heap[--sz]);
        down(0);
        if(view[ver]) continue;
        view[ver] = true;
        dist[ver] = d;
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            if(dist[e[i]] > dist[ver] + w[i])
            {
                dist[e[i]] = dist[ver] + w[i];
                heap[sz++] = { dist[e[i]],e[i] };
                up(sz - 1);
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d %d", &n, &m);
    int a, b, c;
    memset(h, -1, sizeof h);
    while(m--)
    {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d", Dijkstra());
    return 0;
}*/

// 二、存在负权边
/* 1、Bellman-Ford  O(nm) */
// for (n次)
//    for (m次)
//        更新边
// 有边数限制的最短路：https://www.acwing.com/problem/content/855/
/*
const int N = 510, M = 10010;
int dist[N], backup[N];
int n, m, k;
struct Edge{
    int a, b, w;
}edges[M];

bool BellmanFord()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; ++i)
    {
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; ++j)
        {
            auto[a, b, w] = edges[j];
            // if (backup[a] != 0x3f3f3f3f && backup[b] > backup[a] + w) //err
            //     dist[b] = dist[a] + w;
            if (backup[a] != 0x3f3f3f3f && dist[b] > backup[a] + w)
                dist[b] = backup[a] + w;
        }
    }
    if(dist[n] == 0x3f3f3f3f) return false;
    return true;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    int a, b, c;
    for(int i = 0; i < m; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        edges[i] = { a,b,c };
    }
    if(BellmanFord()) printf("%d", dist[n]);
    else puts("impossible");
    return 0;
}*/

/* 2、spfa  一般O(m)，最坏O(nm) */
// 每次将更新过最短距离的点放入队列，再更新其邻接点。
// 如果邻接点更新了，那就继续放入队列...重复此过程，直到队列为空
/*
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool view[N]; //view[i]表示队列中是否有点i
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q; //队列里放到是已更新最短路径的点
    q.push(1);
    view[1] = true;
    while(q.size())
    {
        //拿出已更新的点，去更新其邻接点的最短路径
        int f = q.front(); q.pop();
        view[f] = false;
        for(int i = h[f]; i != -1; i = ne[i])
        {
            if(dist[e[i]] > dist[f] + w[i])
            {
                dist[e[i]] = dist[f] + w[i];
                // 更新了邻接点，并且不在队列中，直接入队
                if(!view[e[i]])
                {
                    q.push(e[i]);
                    view[e[i]] = true;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return false;
    return true;
}
int main()
{
    scanf("%d %d", &n, &m);
    int a, b, c;
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if(spfa()) printf("%d", dist[n]);
    else    puts("impossible");
    return 0;
}*/

/* spfa判断负环 */
/*
const int N = 2010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool view[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; ++i)
    {
        q.push(i);
        view[i] = true;
    }

    while (q.size())
    {
        int f = q.front();
        q.pop();
        view[f] = false;
        for (int i = h[f]; i != -1; i = ne[i])
        {
            if (dist[e[i]] > dist[f] + w[i])
            {
                dist[e[i]] = dist[f] + w[i];
                cnt[e[i]] = cnt[f] + 1;
                if (cnt[e[i]] == n)
                    return true;
                if (!view[e[i]])
                {
                    q.push(e[i]);
                    view[e[i]] = true;
                }
            }
        }
    }
    return false;
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d %d", &n, &m);
    int a, b, c;
    while (m--)
    {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }
    if (spfa())
        puts("Yes");
    else
        puts("No");
    return 0;
}*/

/*********************** 多源最短路径 *************************/
/*********** Floyd  O(n^3) *********/

const int N = 210, INF = 1e9;
int g[N][N];
int n, m, k;

void floyd()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (g[i][k] != INF && g[k][j] != INF && g[i][j] > g[i][k] + g[k][j])
                    g[i][j] = g[i][k] + g[k][j];
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j)
                g[i][j] = 0;
            else
                g[i][j] = INF;

    int a, b, c;
    while (m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    floyd();
    int x, y;
    while (k--)
    {
        scanf("%d%d", &x, &y);
        if (g[x][y] == INF)
            puts("impossible");
        else
            printf("%d\n", g[x][y]);
    }
    return 0;
}
